Differentially%2Dprivate network trace analysis.
Abstract – We consider the potential for network trace analysis while providing the guarantees of “differential privacy.” While differential privacy provably obscures the presence or absence of individual records in a dataset, it has two major limitations: analyses must (presently) be expressed in a higher level declarative language; and the analysis results are randomized before returning to the analyst. We report on our experiences conducting a diverse set of analyses in a differentially private manner. We are able to express all of our target analyses, though for some of them an approximate expression is required to keep the error-level low. By running these analyses on real datasets, we find that the error introduced for the sake of privacy is often (but not always) low even at high levels of privacy. We factor our learning into a toolkit that will be likely useful for other analyses. Overall, we conclude that differential privacy shows promise for a broad class of network analyses. Categories and Subject Descriptors C.2.m [Computer-communication networks] Miscellaneous
A data%2Dparallel toolkit for information retrieval.

Differentially Private Combinatorial Optimization.
Consider the following problem: given a metric space, some of whose points are “clients, ” select a set of at most k facility locations to minimize the average distance from the clients to their nearest facility. This is just the well-studied k-median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. This raises the following quandary: what if the locations of the clients are sensitive information that we would like to keep private? Is it even possible to design good algorithms for this problem that preserve the privacy of the clients? In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the value of an optimal solution, let alone the entire solution. Apart from the k-median problem, we consider the problems of vertex and set cover, min-cut, k-median, facility location, and Steiner tree, and give approximation algorithms and lower bounds for these problems. We also consider the recently introduced submodular maximization problem, “Combinatorial Public Projects ” (CPP), shown by Papadimitriou et al. [28] to be inapproximable to subpolynomial multiplicative factors by any efficient and truthful algorithm. We give a differentially private (and hence approximately truthful) algorithm that achieves a logarithmic additive approximation. 1
A simple and practical algorithm for differentially private data release

Privacy integrated queries an extensible platform for privacy%2Dpreserving data analysis.

Differentially Private Recommender Systems Building Privacy into the Netflix Prize Contenders.
We consider the problem of producing recommendations from collective user behavior while simultaneously providing guarantees of privacy for these users. Specifically, we consider the Netflix Prize data set, and its leading algorithms, adapted to the framework of differential privacy. Unlike prior privacy work concerned with cryptographically securing the computation of recommendations, differential privacy constrains a computation in a way that precludes any inference about the underlying records from its output. Such algorithms necessarily introduce uncertainty— i.e., noise—to computations, trading accuracy for privacy. We find that several of the leading approaches in the Netflix Prize competition can be adapted to provide differential privacy, without significantly degrading their accuracy. To adapt these algorithms, we explicitly factor them into two parts, an aggregation/learning phase that can be performed with differential privacy guarantees, and an individual recommendation phase that uses the learned correlations and an individual’s data to provide personalized recommendations. The adaptations are non-trivial, and involve both careful analysis of the per-record sensitivity of the algorithms to calibrate noise, as well as new post-processing steps to mitigate the impact of this noise. We measure the empirical trade-off between accuracy and privacy in these adaptations, and find that we can provide non-trivial formal privacy guarantees while still outperforming the Cinematch baseline Netflix provides.


Special Issue On The Thirty%2DEighth Annual ACM Symposium On Theory Of Computing %28STOC 2006%29.

Computing Information Retrieval Performance Measures Efficiently in the Presence of Tied Scores.
Abstract. The Information Retrieval community uses a variety of performance measures to evaluate the effectiveness of scoring functions. In this paper, we show how to adapt six popular measures — precision, recall, F1, average precision, reciprocal rank, and normalized discounted cumulative gain — to cope with scoring functions that are likely to assign many tied scores to the results of a search. Tied scores impose only a partial ordering on the results, meaning that there are multiple possible orderings of the result set, each one performing differently. One approach to cope with ties would be to average the performance values across all possible result orderings; but unfortunately, generating result permutations requires super-exponential time. The approach presented in this paper computes precisely the same performance value as the approach of averaging over all permutations, but does so as efficiently as the original, tie-oblivious measures. 1
Data Collection with Self%2DEnforcing Privacy.
Consider a pollster who wishes to collect private, sensitive data from a number of distrustful individuals. How might the pollster convince the respondents that it is trustworthy? Alternately, what mechanism could the respondents insist upon to ensure that mismanagement of their data is detectable and publicly demonstrable? We detail this problem, and provide simple data submission protocols with the properties that a) leakage of private data by the pollster results in evidence of the transgression and b) the evidence cannot be fabricated without breaking cryptographic assumptions. With such guarantees, a responsible pollster could post a “privacy-bond”, forfeited to anyone who can provide evidence of leakage. The respondents are assured that appropriate penalties are applied to a leaky pollster, while the protection from spurious indictment ensures that any honest pollster has no disincentive to participate in such a scheme.
A decentralized algorithm for spectral analysis.
Abstract — The ability of a robot team to reconfigure itself is useful in many applications: for metamorphic robots to change shape, for swarm motion towards a goal, for biological systems to avoid predators, or for mobile buoys to clean up oil spills. In many situations, auxiliary constraints, such as connectivity between team members or limits on the maximum hop-count, must be satisfied during reconfiguration. In this paper, we show that both the estimation and control of the graph connectivity can be accomplished in a decentralized manner. We describe a decentralized estimation procedure that allows each agent to track the algebraic connectivity of a time-varying graph. Based on this estimator, we further propose a decentralized gradient controller for each agent to maintain global connectivity during motion. I.
Mechanism Design via Differential Privacy.
We study the role that privacy-preserving algorithms, which prevent the leakage of specific information about participants, can play in the design of mechanisms for strategic agents, which must encourage players to honestly report information. Specifically, we show that the recent notion of differential privacy [15, 14], in addition to its own intrinsic virtue, can ensure that participants have limited effect on the outcome of the mechanism, and as a consequence have limited incentive to lie. More precisely, mechanisms with differential privacy are approximate dominant strategy under arbitrary player utility functions, are automatically resilient to coalitions, and easily allow repeatability. We study several special cases of the unlimited supply auction problem, providing new results for digital goods auctions, attribute auctions, and auctions with arbitrary structural constraints on the prices. As an important prelude to developing a privacy-preserving auction mechanism, we introduce and study a generalization of previous privacy work that accommodates the high sensitivity of the auction setting, where a single participant may dramatically alter the optimal fixed price, and a slight change in the offered price may take the revenue from optimal to zero. 1
Privacy
Each of two parties PX and P Y holds an n-bit input, x and y, respectively. They wish to privately compute the value of f(x; y). That is, PX should not learn any additional information about y (in the information-theoretic sense) other than what follows from its input x and the function value, f(x; y), and similarly, P Y should not learn any additional information about x.  In this paper we consider two basic questions in the theory of private computations: 1. Which functions can be privately computed ? 2. What is the communication complexity of protocols that privately compute a function  f (in the case that such protocols exist) ? A complete combinatorial characterization of privately computable functions is given. We use this characterization to derive tight bounds on the rounds complexity of any privately computable function, and to design optimal private protocols that compute these functions. We show that for every 1  g(n)  2 \Delta 2  n  there are functions that can be privately...


Fast computation of low%2Drank matrix approximations.
In many practical applications, given an m n matrix A it is of interest to nd an approximation  to A that has low rank. We introduce a technique that exploits spectral structure in  A to accelerate Orthogonal Iteration and Lanczos Iteration, the two most common methods  for computing such approximations. Our technique amounts to independently sampling and/or  quantizing the entries of the input matrix A, thus speeding up computation by reducing the  number of non-zero entries and/or the length of their representation. Our analysis s based on  observing that both sampling and quantization can be viewed as adding a random matrix E to  A, where the entries of E are independent, zero-mean random variables of bounded variance.  Such random matrices posses no signicant linear structure, and we can thus prove that the  eect of sampling and quantization nearly vanishes when a low rank approximation to A is  computed. In fact, the more prominent the linear structure in A is, the more data we can aord  to discard and, ultimately, the faster we can discover it. We give bounds on the quality of our  approximation both in the L2 and in the Frobenius norm.    Author&#039;s address: Microsoft Research, One Microsoft Way, Redmond, WA 98052.  y  Author&#039;s address: Department of Computer Science, University of Washington, Seattle, WA 98105. Research performed while visiting Microsoft Research and supported in part by the Microsoft Corporation.  1 
Data collection with self%2Denforcing privacy.
Consider a pollster who wishes to collect private, sensitive data from a number of distrustful individuals. How might the pollster convince the respondents that it is trustworthy? Alternately, what mechanism could the respondents insist upon to ensure that mismanagement of their data is detectable and publicly demonstrable? We detail this problem, and provide simple data submission protocols with the properties that a) leakage of private data by the pollster results in evidence of the transgression and b) the evidence cannot be fabricated without breaking cryptographic assumptions. With such guarantees, a responsible pollster could post a “privacy-bond”, forfeited to anyone who can provide evidence of leakage. The respondents are assured that appropriate penalties are applied to a leaky pollster, while the protection from spurious indictment ensures that any honest pollster has no disincentive to participate in such a scheme.
Our Data%2C Ourselves Privacy Via Distributed Noise Generation.
Abstract. In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a distributed implementation of the privacy-preserving statistical databases described in recent papers [14,4,13]. In these databases, privacy is obtained by perturbing the true answer to a database query by the addition of a small amount of Gaussian or exponentially distributed random noise. The computational power of evenasimple form of these databases, when the queryis just of the form È i f(di), that is, the sum over all rows i in the database of a function f applied to the data in row i, has been demonstrated in [4]. A distributed implementation eliminates the need for a trusted database administrator. The results for noise generation are of independent interest. The generation of Gaussian noise introduces a technique for distributing shares of many unbiased coins with fewer executions of verifiable secret sharing than would be needed using previous approaches (reduced by afactorofn). The generation of exponentially distributed noise uses two shallow circuits: one for generating many arbitrarily but identically biased coins at an amortized cost of two unbiased random bits apiece, independent of the bias, and the other to combine bits of appropriate biases to obtain an exponential distribution. 1
Calibrating Noise to Sensitivity in Private Data Analysis.
Abstract. We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query function f mapping databases to reals, the so-called true answer is the result of applying f to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user. Previous work focused on the case of noisy sums, in which f =P i g(xi), where xi denotes the ith row of the database and g maps data-base rows to [0, 1]. We extend the study to general functions f, proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f. Roughly speaking, this is the amount that any single argument to f can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case. The first step is a very clean characterization of privacy in terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive. 1 Introduction We continue a line of research initiated in [10, 11] on privacy in statistical data-bases. A statistic is a quantity computed from a sample. Intuitively, if the database is a representative sample of an underlying population, the goal ofa privacy-preserving statistical database is to enable the user to learn properties of the population as a whole while protecting the privacy of the individualcontributors.
On Spectral Learning of Mixtures of Distributions.
We consider the problem of learning mixtures of distributions via spectral methods and derive a tight  characterization of when such methods are useful. Specifically, given a mixture-sample, let  i , C i , w i  denote the empirical mean, covariance matrix, and mixing weight of the i-th component. We prove  that a very simple algorithm, namely spectral projection followed by single-linkage clustering, properly  classifies every point in the sample when each  i is separated from all  j by      2 (1/w i +1/w j )    plus  a term that depends on the concentration properties of the distributions in the mixture. This second term  is very small for many distributions, including Gaussians, Log-concave, and many others. As a result,  we get the best known bounds for learning mixtures of arbitrary Gaussians in terms of the required mean  separation. On the other hand, we prove that given any k means  i and mixing weights w i , there are  (many) sets of matrices C i such that each  i is separated from all  j by      2 (1/w i + 1/w j )    , but  applying spectral projection to the corresponding Gaussian mixture causes it to collapse completely, i.e.,  all means and covariance matrices in the projected mixture are identical.
A First Look at Peer%2Dto%2DPeer Worms Threats and Defenses.
Peer-to-peer (P2P) worms exploit common vulnerabilities in member hosts of a P2P network and spread topologically in the P2P network, a potentially more effective strategy than random scanning for locating victims. This paper describes the danger posed by P2P worms and initiates the study of possible mitigation mechanisms. In particular, the paper explores the feasibility of a self-defense infrastructure inside a P2P network, outlines the challenges, evaluates how well this defense mechanism contains P2P worms, and reveals correlations between containment and the overlay topology of a P2P network. Our experiments suggest a number of design directions to improve the resilience of P2P networks to worm attacks.
Practical privacy the SuLQ framework.
We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to {0, 1}. The true answer is P i∈S f(di), and a noisy version is released as the response to the query. Results of Dinur, Dwork, and Nissim show that a strong form of privacy can be maintained using a surprisingly small amount of noise – much less than the sampling error – provided the total number of queries is sublinear in the number of database rows. We call this query and (slightly) noisy reply the SuLQ (Sub-Linear Queries) primitive. The assumption of sublinearity becomes reasonable as databases grow increasingly large. We extend this work in two ways. First, we modify the privacy analysis to real-valued functions f and arbitrary row types, as a consequence greatly improving the bounds on noise required for privacy. Second, we examine the computational power of the SuLQ primitive. We show that it is very powerful indeed, in that slightly noisy versions of the following computations can be carried out with very few invocations of the primitive: principal component analysis, k means clustering, the Perceptron Algorithm, the ID3 algorithm, and (apparently!) all algorithms that operate in the in the statistical query learning model [11].
Toward Privacy in Public Databases.%2
Abstract. We initiate a theoretical study of the census problem. Informally, in a census individual respondents give private information to a trusted party (the census bureau), who publishes a sanitized version of the data. There are two fundamentally conflicting requirements: privacy for the respondents and utility of the sanitized data. Unlike in the study of secure function evaluation, in which privacy is preserved to the extent possible given a specific functionality goal, in the census problem privacy is paramount; intuitively, things that cannot be learned “safely ” should not be learned at all. An important contribution of this work is a definition of privacy (and privacy compromise) for statistical databases, together with a method for describing and comparing the privacy offered by specific sanitization techniques. We obtain several privacy results using two different sanitization techniques, and then show how to combine them via cross training. We also obtain two utility results involving clustering. 1
On profit%2Dmaximizing envy%2Dfree pricing.
 We consider a Stackelberg pricing problem in directed, uncapacitated networks. Tariffs have to be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs are assumed to be given. There are n clients, the followers, that route their demand independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator’s revenue. Motivated by problems in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator’s tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX-hard. Moreover, we show that uniform pricing yields both an m–approximation, and a (1 + ln D)–approximation. Here, D is upper bounded by the total demand of all clients. We furthermore discuss some polynomially solvable special cases, and present a short computational study with instances from France Télécom. In addition, we consider the problem under the additional restriction that the operator must serve all clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless NP = ZPP, and we prove the existence of an n–approximation algorithm. 
Toward Privacy in Public Databases.%2
Abstract. We initiate a theoretical study of the census problem. Informally, in a census individual respondents give private information to a trusted party (the census bureau), who publishes a sanitized version of the data. There are two fundamentally conflicting requirements: privacy for the respondents and utility of the sanitized data. Unlike in the study of secure function evaluation, in which privacy is preserved to the extent possible given a specific functionality goal, in the census problem privacy is paramount; intuitively, things that cannot be learned “safely ” should not be learned at all. An important contribution of this work is a definition of privacy (and privacy compromise) for statistical databases, together with a method for describing and comparing the privacy offered by specific sanitization techniques. We obtain several privacy results using two different sanitization techniques, and then show how to combine them via cross training. We also obtain two utility results involving clustering. 1
On Privacy%2DPreserving Histograms.
In a census, individual respondents give private information to a trusted party (the census bureau), who publishes a sanitized version of the data. There are two fundamentally conflicting requirements: privacy for the respondents and utility of the sanitized data. Note that this framework is inherently noninteractive. Recently, Chawla et al. (TCC’2005) initiated a theoretical study of the census problem and presented an intuitively appealing definition of privacy breach, called isolation, together with a formal specification of what is required from a data sanitization algorithm: access to the sanitized data should not increase an adversary’s ability to isolate any individual. They also showed that if the data are drawn uniformly from a highdimensional hypercube then recursive histogram sanitization can preserve privacy with a high probability. We extend these results in several ways. First, we develop a method for computing a privacy-preserving histogram sanitization of “round ” distributions, such as the uniform distribution over a high-dimensional ball or sphere. This problem is quite challenging because, unlike for the hypercube, the natural histogram over such a distribution may have long and thin cells that hurt the proof of privacy. We then develop techniques for randomizing the histogram constructions both for the hypercube and the hypersphere. These permit us to apply known results for approximating various quantities of interest (e.g., cost of the minimum spanning tree, or the cost of an optimal solution to the facility location problem over the data points) from histogram counts – in a privacy-preserving fashion. 1
A uniform approach to accelerated PageRank computation.
In this note we consider a simple reformulation of the traditional power iteration algorithm for computing the stationary distribution of a Markov chain. Rather than communicate their current probability values to their neighbors at each step, nodes instead communicate only changes in probability value. This reformulation enables a large degree of flexibility in the manner in which nodes update their values, leading to an array of optimizations and features, including faster convergence, e#cient incremental updating, and a robust distributed implementation.
Spectral Analysis of Random Graphs with Skewed Degree Distributions.
We extend spectral methods to random graphs with skewed degree distributions through a degree based normalization closely connected to the normalized Laplacian. The normalization is based on intuition drawn from perturbation theory of random matrices, and has the effect of boosting the expectation of the random adjacency matrix without increasing the variances of its entries, leading to better perturbation bounds. The primary implication of this result lies in the realm of spectral analysis of random graphs with skewed degree distributions, such as the ubiquitous “power law graphs”. Recently Mihail and Papadimitriou [22] argued that for randomly generated graphs satisfying a power law degree distribution, spectral analysis of the adjacency matrix will simply produce the neighborhoods of the high degree nodes as its eigenvectors, and thus miss any embedded structure. We present a generalization of their model, incorporating latent structure, and prove that after applying our transformation, spectral analysis succeeds in recovering the latent structure with high probability.
A decentralized algorithm for spectral analysis.
Abstract — The ability of a robot team to reconfigure itself is useful in many applications: for metamorphic robots to change shape, for swarm motion towards a goal, for biological systems to avoid predators, or for mobile buoys to clean up oil spills. In many situations, auxiliary constraints, such as connectivity between team members or limits on the maximum hop-count, must be satisfied during reconfiguration. In this paper, we show that both the estimation and control of the graph connectivity can be accomplished in a decentralized manner. We describe a decentralized estimation procedure that allows each agent to track the algebraic connectivity of a time-varying graph. Based on this estimator, we further propose a decentralized gradient controller for each agent to maintain global connectivity during motion. I.
Web Search via Hub Synthesis.
We present a model for web search that captures in a unified manner three critical components of the problem: how the link structure of the web is generated, how the content of a web document is generated, and how a human searcher generates a query. The key to this unification lies in capturing the correlations between these components in terms of proximity in a shared latent semantic space. Given such a combined model, the correct answer to a search query is well defined, and thus it becomes possible to evaluate web search algorithms rigorously. We present a new web search algorithm, based on spectral techniques, and prove that it is guaranteed to produce an approximately correct answer in our model. The algorithm assumes no knowledge of the model, and is well-defined regardless of the model&#039;s accuracy. 1. 
Spectral Partitioning of Random Graphs.
Problems such as bisection, graph coloring, and clique are generally believed hard in the worst case. However, they can be solved if the input data is drawn randomly from a distribution over graphs containing acceptable solutions. In this paper we show that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. In nearly all cases our approach meets or exceeds previous parameters, while introducing substantial generality. We apply spectral techniques, using foremost the observation that in all of these problems, the expected adjacency matrix is a low rank matrix wherein the structure of the solution is evident.  1 
Sampling Techniques for Kernel Methods.
We propose randomized techniques for speeding up Kernel Principal  Component Analysis on three levels: sampling and quantization of the  Gram matrix in training, randomized rounding in evaluating the kernel  expansions, and random projections in evaluating the kernel itself. In all  three cases, we give sharp bounds on the accuracy of the obtained approximations.
Fast computation of low rank matrix.
In many practical applications, given an m n matrix A it is of interest to nd an approximation  to A that has low rank. We introduce a technique that exploits spectral structure in  A to accelerate Orthogonal Iteration and Lanczos Iteration, the two most common methods  for computing such approximations. Our technique amounts to independently sampling and/or  quantizing the entries of the input matrix A, thus speeding up computation by reducing the  number of non-zero entries and/or the length of their representation. Our analysis s based on  observing that both sampling and quantization can be viewed as adding a random matrix E to  A, where the entries of E are independent, zero-mean random variables of bounded variance.  Such random matrices posses no signicant linear structure, and we can thus prove that the  eect of sampling and quantization nearly vanishes when a low rank approximation to A is  computed. In fact, the more prominent the linear structure in A is, the more data we can aord  to discard and, ultimately, the faster we can discover it. We give bounds on the quality of our  approximation both in the L2 and in the Frobenius norm.    Author&#039;s address: Microsoft Research, One Microsoft Way, Redmond, WA 98052.  y  Author&#039;s address: Department of Computer Science, University of Washington, Seattle, WA 98105. Research performed while visiting Microsoft Research and supported in part by the Microsoft Corporation.  1 
Spectral analysis of data.

